using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;

namespace LevelEditor
{
    public class OctTree<T>
        where T : struct
    {
        private class OctTreeNode
        {
            public T? value;

            public float radius;

            public BoundingBox region
            {
                get { return new BoundingBox(center - new Vector3(radius), center + new Vector3(radius)); }
            }

            public List<OctTreeNode> children;

            public OctTreeNode parent;

            public int depth;

            public bool IsLeaf
            {
                get { return children == null; }
            }

            public Vector3 center;

            public OctTreeNode(T? value, Vector3 center, float radius, OctTreeNode parent)
            {
                this.value = value;
                this.center = center;
                this.radius = radius;
                this.parent = parent;
                if (parent != null)
                    depth = parent.depth + 1;
            }

            public void Devide()
            {
                float half_radius = radius / 2.0f;
                children = new List<OctTreeNode>();
                // left top back
                children.Add(new OctTreeNode(null, center + new Vector3(half_radius, half_radius, half_radius), half_radius, this));
                // left top front
                children.Add(new OctTreeNode(null, center + new Vector3(half_radius, half_radius, -half_radius), half_radius, this));
                // left bottom back
                children.Add(new OctTreeNode(null, center + new Vector3(half_radius, -half_radius, half_radius), half_radius, this));
                // left bottom front
                children.Add(new OctTreeNode(null, center + new Vector3(half_radius, -half_radius, -half_radius), half_radius, this));
                // right top back
                children.Add(new OctTreeNode(null, center + new Vector3(-half_radius, half_radius, half_radius), half_radius, this));
                // right top front
                children.Add(new OctTreeNode(null, center + new Vector3(-half_radius, half_radius, -half_radius), half_radius, this));
                // right bottom back
                children.Add(new OctTreeNode(null, center + new Vector3(-half_radius, -half_radius, half_radius), half_radius, this));
                // right bottom front
                children.Add(new OctTreeNode(null, center + new Vector3(-half_radius, -half_radius, -half_radius), half_radius, this));
            }

            public OctTreeNode GetLeaf(Vector3 position)
            {
                OctTreeNode iter = this;
                while (true)
                {
                    if (iter.IsLeaf)
                        return iter;

                    Vector3 diff = position - iter.center;
                    if (diff.X > 0)
                    {
                        if (diff.Y > 0)
                        {
                            if (diff.Z > 0)
                                iter = iter.children[0];
                            else
                                iter = iter.children[1];
                        }
                        else
                        {
                            if (diff.Z > 0)
                                iter = iter.children[2];
                            else
                                iter = iter.children[3];
                        }
                    }
                    else
                    {
                        if (diff.Y > 0)
                        {
                            if (diff.Z > 0)
                                iter = iter.children[4];
                            else
                                iter = iter.children[5];
                        }
                        else
                        {
                            if (diff.Z > 0)
                                iter = iter.children[6];
                            else
                                iter = iter.children[7];
                        }
                    }
                }
            }
        }

        OctTreeNode root;

        float radius;

        public OctTree(float radius)
        {
            this.radius = radius;
        }

        public void Add(T? value, Vector3 position)
        {
            if (root == null)
            {
                root = new OctTreeNode(null, Vector3.Zero, radius, null);
                root.Devide();
            }

            OctTreeNode iter = root.GetLeaf(position);
            while (iter.radius > 1)
            {
                iter.Devide();
                iter = iter.GetLeaf(position);
            }
            iter.value = value;
        }

        public void Clear()
        {
            root = null;
        }

        public T? this[Vector3 position]
        {
            get { return root.GetLeaf(position).value; }
            set 
            {
                OctTreeNode leaf = root.GetLeaf(position);
                leaf.value = value;
            }
        }
    }
}